class MyLinkedList {
  constructor() {
    this.head = new Node();
    this.last = new Node();
    this.size = 0;
  }
  insert (index, data) {
    if (index < 0 || index > this.size) {
      throw Error('超出节点范围');
    }
    let insertNode = new Node(data);
    if (this.size == 0) {
      //空链表
      this.head = insertNode;
      this.last = insertNode;
    } else if (index == 0) {
      //插入头部
      insertNode.next = this.head;
      this.head = insertNode;
    } else if (index == this.size) {
      //插入尾部
      this.last.next = insertNode;
      this.last = insertNode;
    } else {
      //插入中间
      let prevNode = this.get(index - 1);
      insertNode.next = prevNode.next;
      prevNode.next = insertNode;
    }
    this.size++;
  }
  /**
   * 
   * @param  index  查找的位置
   */
  get (index) {
    if (index < 0 || index >= this.size) {
      throw Error('超出节点范围');
    }
    let temp = this.head;
    for (let i = 0; i < index; i++) {
      temp = temp.next;
    }
    return temp;
  }
  /**
   *  @param  index  删除的位置
   */
  remove (index) {
    if (index < 0 || index >= this.size) {
      throw Error('超出节点范围');
    }
    let removeNode;
    if (index == 0) {
      //删除头节点
      removeNode = this.head;
      this.head = this.head.next;
    } else if (index == this.size - 1) {
      //删除尾节点
      let prevNode = this.get(index - 1);
      removeNode = prevNode.next;
      prevNode.next = null;
      this.last = prevNode;
    } else {
      //删除中间节点
      let prevNode = this.get(index - 1);
      let nextNode = prevNode.next.next;
      removeNode = prevNode.next;
      prevNode.next = nextNode;
    }
    this.size--;
    return removeNode;
  }
  output () {
    let temp = this.head;
    while (temp != null) {
      console.log(temp.data);
      temp = temp.next;
    }
  }
}
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

let myLinkedList = new MyLinkedList();
myLinkedList.insert(0, 3);
myLinkedList.insert(0, 4);
myLinkedList.insert(2, 9);
myLinkedList.insert(3, 5);
myLinkedList.insert(1, 6);
myLinkedList.remove(0);
myLinkedList.output();